/**
 * 这是 LeetCode 125. 验证回文串
 * https://leetcode.cn/problems/valid-palindrome
 */
import static org.junit.Assert.assertEquals;

class ValidPalindrome {

/**
 * 方法：isPalindrome
 * 逻辑: 使用双指针方法判断字符串是否为回文。
 * Args: s - 输入字符串
 * Returns: 如果字符串是回文，返回true；否则返回false
 * Time: O(n) - 需要遍历字符串一次
 * Space: O(1) - 只使用了常数级的额外空间
 */
public boolean isPalindrome(String s) {
    int len = s.length();
    if(len <= 1) return true;
    int left = 0; int right = len - 1;
    while(left < right){
        while(left < right && !Character.isLetterOrDigit(s.charAt(left))){
            ++left;
        }
        while(left < right && !Character.isLetterOrDigit(s.charAt(right))){
            --right;
        }
        if(left < right){
            if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))){
                return false;
            }
            ++left;
            --right;
        }
    }
    return true;
}

/**
 * 方法：isPalindrome1
 * 逻辑: 使用字符串缓冲区判断字符串是否为回文。
 * Args: s - 输入字符串
 * Returns: 如果字符串是回文，返回true；否则返回false
 * Time: O(n) - 需要遍历字符串两次
 * Space: O(n) - 使用了字符串缓冲区存储字符
 */
public boolean isPalindrome1(String s) {
    StringBuffer b = new StringBuffer();
    for (int i = 0; i < s.length(); i++) {
        if (Character.isLetterOrDigit(s.charAt(i))) {
            b.append(Character.toLowerCase(s.charAt(i)));
        }
    }
    StringBuffer c = new StringBuffer(b.toString());
    c.reverse();
    return c.toString().equals(b.toString());
}

/**
 * 方法：testIsPalindrome
 * 逻辑: 测试isPalindrome方法的正确性。
 * Args: 无
 * Returns: 无
 * Time: O(n) - 取决于测试用例的数量和长度
 * Space: O(1) - 只使用了常数级的额外空间
 */
public void testIsPalindrome() {
    ValidPalindrome solution = new ValidPalindrome();

    // Test Case 1: A simple palindrome
    String s1 = "A man, a plan, a canal: Panama";
    boolean expected1 = true;
    boolean actual1 = solution.isPalindrome(s1);
    assertEquals(expected1, actual1);

    // Test Case 2: Not a palindrome
    String s2 = "Not a palindrome";
    boolean expected2 = false;
    boolean actual2 = solution.isPalindrome(s2);
    assertEquals(expected2, actual2);

    // Test Case 3: Single character
    String s3 = "a";
    boolean expected3 = true;
    boolean actual3 = solution.isPalindrome(s3);
    assertEquals(expected3, actual3);

    // Test Case 4: Empty string
    String s4 = "";
    boolean expected4 = true;
    boolean actual4 = solution.isPalindrome(s4);
    assertEquals(expected4, actual4);

    System.out.println("All test cases passed successfully!");
}

/**
 * 方法：main
 * 逻辑: 运行测试方法。
 * Args: args - 命令行参数
 * Returns: 无
 * Time: O(n) - 取决于测试用例的数量和长度
 * Space: O(1) - 只使用了常数级的额外空间
 */
public static void main(String[] args) {
    ValidPalindrome solution = new ValidPalindrome();
    try {
        solution.testIsPalindrome();
        System.out.println("\nAll test cases passed successfully!");
    } catch (AssertionError e) {
        System.out.println("\nTest failed: " + e.getMessage());
    }
}
}
